Advances in computer hardware and software technology have brought about increasing uses of digital imagery. However, the amount of memory necessary to store a large number of high resolution digital images is significant. Furthermore, the time and bandwidth necessary to transmit the images is unacceptable for many applications. Accordingly, there has been considerable interest in the field of digital image compression.
The basic elements of a digital image compression system are shown schematically in FIG. 1, and are referenced by those elements contained within dotted line box 100. A digitized image is processed by an encoder 101 to reduce the amount of information required to reproduce the image. This information is then typically stored as compressed data in a memory 102. When the image is to be reconstructed, the information stored in memory 102 is passed through a decoder 103.
The goal of a good compression method implemented by encoder 101 is to attain a high compression ratio with minimal loss in fidelity. One of the latest approaches to the image compression problem has been put forth by Arnaud Jacquin in a paper entitled "Fractal Image Coding Based on a Theory of Iterated Contractive Image Transformations", appearing in The International Society for Optical Engineering Proceedings Volume 1360, Visual Communications and Image Processing, October 1990, pp. 227-239. As is known in the art, fractal image generation is based on the iteration of simple deterministic mathematical procedures that can generate images with infinitely intricate geometries (i.e. fractal images). However, to use these fractal procedures in digital image compression, the inverse problem of constraining the fractal complexity to match the given complexity of a real-world image must be solved. The "iterated transformation" method of Jacquin constructs, for each original image, a set of transformations which form a map that encodes the original image. Each transformation maps a portion of the image to another portion of the image. The transformations, when iterated, produce a sequence of images which converge to a fractal approximation of the original image.
In order for a transformation to map onto some portion of the original image within a specified error bound, the transformation must be optimized in terms of position, size and intensity. Further, a fundamental requirement of Jacquin's iterated transformation method is that each transformation is constrained to be "contractive". Contractivity means that the size and intensity of a transformation are scaled down relative to that portion of the original image from which it is being mapped. However, restricting acceptable transformations to those that are contractive reduces the total number of possible transformations that may be chosen.
Thus, the need exists for a method of encoding an original digital image using iterated transformation techniques that expands the total number of possible transformations in order to determine a better set of transformations that encode an image. Accordingly, it is an object of the present invention to provide a method of encoding an image using iterated transformation techniques that maximizes image compression while minimizing loss in fidelity.